import java.util.ArrayList;
/**
 * 快速排序
 * 递归实现
 */
public class quickSort {
    public void quickSort(int[] arr) {
        helper(arr, 0, arr.length - 1);
    }

    public void helper(int[] arr, int low, int high) {
        /**
         * 如果low=high，说明只有一个元素，也就不需要排序了
         */
        if (low < high) {
            int p = partition(arr, low, high);
            helper(arr, low, p - 1);
            helper(arr, p + 1, high);
        }
    }

    /**
     * 快速排序经典的分区算法,用左边元素作为枢纽元
     * 使用该函数的前提条件：left < right
     * @param input
     * @param left
     * @param right
     * @return
     */
    private int partition(int[] input, int left, int right) {
        int pivot = input[left];
        int low = left + 1, high = right;
        while (true) {
            /**
            * 找到第一个比pivot小的数
            * 为保证排序稳定性，等于pivot的数不移动
            * 加low < right,保证index不会超出right
            */
            while (pivot >= input[low] && low < right) {
                low++;
            }
            /**
            * 找到第一个比pivot大的数
            * 加high > left,保证high小于枢纽元的index
            */
            while (pivot < input[high] && high > left) {
                high--;
            }
            if (low < high) {
                swap(input, low, high);
            } else {
                break;
            }
        }
        swap(input, left, high);
        return high;
    }

    private void swap(int[] input, int i, int j) {
        int tmp = input[i];
        input[i] = input[j];
        input[j] = tmp;
    }

    /**
     * @deprecated:可以跑通,但是难以理解
     * 快速排序经典的分区算法,用右边元素作为枢纽元
     * 使用该函数的前提条件：low < high
     * @param input
     * @param left
     * @param right
     * @return
     */
    private int partition_right(int[] input, int low, int high) {
        int pivot = input[high];
        int i = low-1;
        for (int j = low; j < high; j++) {
            if (input[j] < pivot) {
                i++;
                swap(input, i, j);
            }
        }
        swap(input, i+1, high);
        return i+1;
    }

}
